这个题目有比下面的描述容易得多的具体做法，所以我这题解看一乐就行

转化

对每个 $k$, 设 $p_k$ 为排列, 其中 $p_k(i) = \text{从城市 $i$ 出发走编号为 $k$ 的虫洞到达的城市编号}$, 那么问题转化为:

给定 $n$, 以及 $m$ 个 $n$ 个数的排列 $p_1, \dots, p_m$, 使得给出的排列两两交换 (即 $p_i(p_j(x)) = p_j(p_i(x))$). 问有多少种办法再选取 $k$ 个排列 $p_{m+1}, \dots, p_{m+k}$, 使得所有 $p_1, \dots, p_{m+k}$ 之间两两交换.

约定

本题解使用了一些抽象代数和线性代数的方法和结论. 虽然有办法不涉及代数，纯使用组合语言说明，但是将比较冗杂。

题解中出现的记号解释如下:

• $[n]$ 表示 $\{1, \dots, n\}$ 这个集合.
• 对一个 $n$ 置换 $p$ 以及一个数 $x \in [n]$, 记 $px = p(x)$ 是 $x$ 被 $p$ 打到的像。
• $\mathbb{Z}^n$ 表示 $n$ 个 $\mathbb{Z}$ 的直和（乘积）这个群，即所有 $n$ 维整数向量在加法下构成的群。

我们不区分“置换”和“排列”这两个词，所有排列都是 $1, \dots, n$ 的排列。

进一步转化

设 $m$ 个排列 $p_1, \dots, p_m$, 使得它们两两交换，则由这些排列可以定义 $\mathbb{Z}^m$ 在 $[n]$ 上的群作用： (换言之，定义了 $\mathbb{Z}^m$ 到 $n$ 元对称群 $\mathfrak{S}_n$ 的群同态).

$$\begin{aligned} \mathbb{Z}^m \times [n] &\to [n] \\ ((a_1, \dots, a_m), x) &\mapsto p_1^{a_1} p_2^{a_2} \dots p_m^{a_m} x. \end{aligned}$$

因此，问题变成了： 给出 $\mathbb{Z}^m$ 在 $[n]$ 上的群作用，求它能扩展成多少种 $\mathbb{Z}^{m+k}$ 在 $[n]$ 上的群作用。

一个引理

设群 $G$ 作用在集合 $X$ 上。那么 $X$ 里一个元素在 $G$ 的作用下能变成的元素构成的集合称为一个轨道。 如果 $X$ 里只有一个轨道，就说这个群作用是传递的。

显然，不传递的群作用可以分拆成若干个传递的群作用。 比如 $\mathbb{Z}$ 通过排列 $p$ 作用在 $[n]$ 上，那么 $p$ 的每一个轮换构成一个轨道。

我们陈述这样一个引理：

引理： 设 Abel 群（即交换群） $G$ 作用在集合 $[n]$ 上，且这个群作用是传递的。任取 $x \in [n]$, 记 $H = \{ g \in G \mid g x = x \}$ （这个子群称为稳定子群）。 那么 $H$ 不依赖于 $x$ 的选取（即选择不同的 $x$ 会给出相同的 $H$), 且 $G$ 在 $[n]$ 上的作用等价于 $G$ 在商群 $G/H$ 上的作用（因此 $|G/H| = n$）。 进一步地，对每个满足 $|G/H|=n$ 的子群 $H$，都恰好存在 $(n-1)!$ 种 $G$ 在 $[n]$ 上的作用，使得其稳定子群是 $H$.

证明： 我们仅叙述证明思路。若选取两个 $x, y \in [n]$，由于作用传递，存在 $p \in G$ 使得 $px=y$。因此 $gy=y \iff gpx=px \iff p(gx)=px \iff gx=x$. 所以 $H$ 不依赖于 $x$ 的选取。第二个声称（群作用的等价）是容易的。 对第三个声称，可以给 $G/H$ 的每个点标 $1~n$ 的编号，就给出了 $G$ 在 $[n]$ 上的作用；一共有 $n!$ 种编号方式，不过每 $n$ 种给出同一个作用。所以共有 $(n-1)!$ 个作用。

$\mathbb{Z}^m$ 的子群

根据上面的引理，我们需要找到 $\mathbb{Z}^m$ 的所有子群 $H$，使得 $\mathbb{Z}^m / H$ 是有限集。更进一步地我们还希望能简单地不重不漏枚举出所有这样的 $H$。

根据一些有限生成 Abel 群结构定理，如果 $H \subset \mathbb{Z}^m$ 是一个子群，那么必然存在一个 $m \times m$ 的整数矩阵 $A$，使得（如果把 $\mathbb{Z}^m$ 的元素看作行向量）

$$ H = \{ x \in \mathbb{Z}^m \mid Ax = 0 \}. $$

不同的 $A$ 有可能给出相同的 $H$：如果 $A = PB$，其中 $P$ 可逆且 $P$ 和 $P^{-1}$ 都是整系数矩阵（这个条件等价于说 $P$ 是行列式 $\pm 1$ 的整系数矩阵）， 那么 $A$ 和 $B$ 给出的 $H$ 显然是相同的；反之也同样，即如果 $A, B$ 给出相同的 $H$，那么存在满足这个条件的 $P$ 使得 $A = PB$.

我们称满足 $A = PB$ 且 $P$ 和 $P^{-1}$ 都是整系数矩阵的两个矩阵 $A, B$ 行等价。 因此，要枚举所有 $H$，就是要找出整系数矩阵在行等价关系下的等价类。

这个等价类可以由 Hermite 标准型给出：每个整系数矩阵都行等价于唯一一个矩阵 $N$，满足如下三条： 设 $a_i$ 是最小的使得 $H_{i,a_i} \neq 0$ 的下标，称 $H$ 中 $(i, a_i)$ 位置的元素为“主元”，则： - $H$ 中每个主元都非负； - 对 $H$ 中每一个主元所在的列，它上面的元素都是小于这个主元的非负整数，它下面的元素都是 $0$； - $H$ 中每一行的主元都在上一行的主元的右边。

换言之，$H$ 是一个行阶梯矩阵，且每一行的第一个非零元（主元）都非负，且主元上面的元素都是小于它的非零元素。

从 $A$ 得到他的标准型 $N$ 的过程如下：计算第一列所有元素的 $\gcd$，设为 $d$，通过初等行变换把 $a_{1,1}$ 变成 $d$（扩展 Euclid 算法）， 然后用第一行消掉下面的每一行的第一个数；接下来再做第二列，以此类推。每得到某一行的主元 $x$，就用它去消上面的行，使得 $x$ 正上方的元素都在 $[0, x)$ 范围内。

标准型的唯一性我们不证，因为对算法没有贡献。

进一步地，我们只需要那些 $\mathbb{Z}^m/H$ 有限的子群 $H$。这样的 $H$ 对应的矩阵 $A$ 一定具有非零行列式，且这个行列式的绝对值就是 $|\mathbb{Z}^m/H|$。 因此标准型 $N$ 是一个主对角线都是正整数的阶梯矩阵。

$m=0$ 的情形

我们有了手上的工具，已经可以解决题目的一个特例：$m=0$ 的情况.

我们要求出 $\mathbb{Z}^k$ 在 $[n]$ 上的群作用个数。先考虑传递的群作用个数。

根据上面的讨论，问题转化为：有多少个 $k \times k$ 的 Hermite 标准型阵，使得其特征值是 $n$？这个问题的答案乘以 $(n-1)!$ 就是传递作用的个数。

只需要枚举 Hermite 标准型的对角线元素。设对角线元素依次是 $d_1, \dots, d_k$，那么行列式是 $d_1 d_2 \dots d_k = n$。 $d_i$ 上方的 $i-1$ 个元素可以在 $[0, d_i)$ 中任取，因此一共有

$$ \lambda_k(n) = \sum_{d_1 d_2 \dots d_k = n} d_2 d_3^2 \dots d_k^{k-1} $$

种行列式为 $n$ 的 $k \times k$ Hermite 标准型，从而有 $\lambda_k(n) (n-1)!$ 种传递作用。

对于不传递的情况，可以用生成函数解决。因为我们要把 $[n]$ 分成若干个部分，每个部分各自独立地定义一个传递作用。也就是带标号的分拆。 因此设 $F_k(x) = \sum_n a_n \frac{x^n}{n!}$ 为指数型生成函数，其中 $a_n$ 是 $\mathbb{Z}^k$ 在 $[n]$ 上的作用个数；则

$$ F_k(x) = \exp\Bigl( \sum_n \lambda_k(n) (n-1)! \frac{x^n}{n!} \Bigr). $$

若对每个 $i \in [1, n]$ 计算出了 $\lambda_k(i)$，则多项式 FFT 即可计算 $F$。 对于计算 $\lambda_k$，注意到它是积性函数，所以只需要计算他在素数幂处的值。 而

$$ \sum_i \lambda_k(p^i) x^i = \prod_{j=0}^{k-1} \frac{1}{1 - p^j x} = \exp\Bigl( \sum_i \sum_{j=0}^{k-1} p^{ij} x^j \Bigr) $$

等比数列求和之后多项式 exp 即可 （这个长为 logn 的多项式 exp 暴力算就行了）.

对输入的处理

输入给定了 $m$ 个排列，也就是 $\mathbb{Z}^m$ 在 $[n]$ 上的一个作用。 我们希望把这个输入的作用拆成轨道，并按上面说的找到对应的子群的矩阵的 Hermite 标准型。

拆成轨道是容易的：其实就是找输入的图的连通分支（因为是群作用，所以连通分支也是强连通分支）。 每个轨道可以分别处理，所以我们现在考虑一个轨道，看看怎么找到对应的子群的矩阵的 Hermite 标准型。

为了方便叙述，设这个轨道是 $[n] = \{ 1, \dots, n \}$. 通过找路径，我们可以对每个点 $k$ 找到一个 $v_k \in \mathbb{Z}^m$， 使得 $q_k(1) = k$，其中 $q_k$ 是 $v_k$ 对应的置换。 那么我们事实上已经得到了商群 $\mathbb{Z}^m / H$ 的结构：这个商群恰好由 $q_1, \dots, q_n$ 构成（根据交换条件容易知道 $q_i q_j = q_{q_i(j)}，所以乘法表就是复合）。 也就是说我们已经得到了商群的乘法表。

这一段懒得写了，都知道乘法表了还只需要 $n^2$ 算自然是想怎么算怎么算.

总之我们可以算出商群的结构（分解成若干个循环乘积），因此得到一组关系，也就是一个矩阵，然后算它的行标准型即可。 事实上根据下面的做法，我们只要判断这样的子群是否相等。或许有一些简单做法吧。暂时懒得想了。

总结

先考虑输入的群作用传递的情况。这时候问题变成有多少个 $\mathbb{Z}^{m+k}$ 的子群 $N'$ 使得 $N' \cap \mathbb{Z}^m = N$, 那 $N'$ 对应的 Hermite 标准型的右下 $m \times m$ 和 $N$ 一样，左上的对角元素都是 $1$。而右上一共有 $k$ 行 $m$ 列不确定。 显然一共有 $n^k$ 种选法。其实就是只能选上一节里面 $q_1, \dots, q_n$ 这些排列。

考虑输入的群作用不传递的情况。我们把输入的群作用划分轨道，设第 $j$ 个轨道对应的子群是 $H_j$，矩阵是 $N_j$. 那么群作用扩张之后，有些轨道会合并。由于群作用的对称性和交换性，容易知道只有作为群作用同构（$H_j = H_{j'}$）的轨道才可能合并。 因此每种不同的 $H_j$ 的部分可以分别计算，最后将方案数做乘积。

现在考虑 $H_j$ 相同的部分。设 $H = H_j$，且一共有 $l$ 个这样的轨道，$n = l |H|$. 类似 $m=0$ 的情形，先计算最后的群作用是传递的方案数， 也就是计算有多少个行列式为 $n$ 的 $(m+k) \times (m+k)$ 矩阵，使得其的右下 $m \times m$ 部分等于 $N_j$. 不难得知方案数是 $\lambda_k(l) |H|^k$. 不过系数并不是 $(n-1)!$，因为右下 $m$ 个的作用已经固定了；可以这样计算： 设群是 $K$，$H \subset K$，那么这样的作用个数如下：取 $H$ 在 $K$ 中的 $l$ 个陪集的代表元， 每个代表元可以选择一个轨道里的一个元素，总方案数是 $l!|H|^l$；不过 $H$ 的作用下每 $n$ 个选取给出同一个作用， 所以事实上的方案数是 $(l-1)!|H|^{l-1}$. 也就是说方案是 $\lambda_k(l) (l-1)! |H|^{l-1+k}$.

因此，未必传递的方案数就是

$$ l! [x^l] \exp\Bigl( \sum_i \lambda_k(i) (i-1)! |H|^{k+i-1} \frac{x^i}{i!} \Bigr). $$

根据 $m=0$ 的做法的办法去做就可以了。